/**
 * 55. 跳跃游戏
 */
public class Solution_55 {
    /**
     * 官方题解：贪心
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     */
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int rightMost = 0;
        for (int i = 0; i < len; i++) {
            if (i <= rightMost) {
                rightMost = Math.max(rightMost, i + nums[i]);
                if (rightMost >= len - 1) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution_55 solution = new Solution_55();
        int[] nums1 = { 2, 3, 1, 1, 4 };
        boolean ans1 = solution.canJump(nums1);
        System.out.println(ans1);
        int[] nums2 = { 3, 2, 1, 0, 4 };
        boolean ans2 = solution.canJump(nums2);
        System.out.println(ans2);
    }
}
